package com.wm.algorithm.array;

import java.util.*;

/**
 * @ClassName: DifficultyArray
 * @Description: 困难级别
 * @Author: WM
 * @Date: 2021-07-24 23:08
 **/
public class DifficultyArray {

    public static void main(String[] args) {
        String s = "ADOBECODEBANC";
        String t = "ABC";
        System.out.println(minWindow(s, t));
    }


    /**
     * 312. 戳气球
     * https://leetcode.cn/problems/burst-balloons/
     * 方法：动态规划
     * 思路：戳气球涉及相邻两个气球的标号的计算，考虑两端的气球，所以定义一个新数组points[n+2]，提前将戳两端气球需要设置默认计算
     * 的两个虚拟气球算进去。定义dp数组dp[i][j]，表示戳破气球的最大得分，所戳破的气球位置是k，其相邻的两个气球的位置分别是i，j。
     * (i<k<j)。i和j就是两个「状态」，最后戳破的那个气球k就是「选择」。
     * 最后戳破气球k，那得先把开区间(i, k)的气球都戳破，再把开区间(k, j)的气球都戳破；最后剩下的气球k，相邻的就是气球i和气球j
     * 状态转移方程：dp[i][j]=Math.max(dp[i][j],points[i-1]*points[i]*points[i+1])。
     * base case：dp数组初始化为0
     * 状态列举：两个指针i，j从数组的末端向前移动，二者之间的区间里面找到最后戳破的气球是哪个，即最优的k位置的气球
     *
     * @param nums
     * @return
     */
    // O(n^3)/O(n^2)
    public int maxCoins(int[] nums) {
        int n = nums.length;
        // 添加两侧的虚拟气球
        int m = n + 2;
        int[] points = new int[m];
        points[0] = points[n + 1] = 1;
        for (int i = 1; i <= n; i++) {
            points[i] = nums[i - 1];
        }

        // base case 已经都被初始化为 0
        int[][] dp = new int[m][m];
        // 开始状态转移
        for (int i = n; i >= 0; i--) {
            for (int j = i + 1; j < m; j++) {
                // 最后戳破的气球是哪个？
                for (int k = i + 1; k < j; k++) {
                    // 择优做选择
                    dp[i][j] = Math.max(dp[i][j],
                            dp[i][k] + dp[k][j] + points[i] * points[k] * points[j]);
                }

            }

        }
        return dp[0][n + 1];
    }

    /**
     * 887. 鸡蛋掉落
     * https://leetcode.cn/problems/super-egg-drop/
     * 方法：动态规划
     * 思路：动态转移方程：dp 数组的定义：dp[k][m] = n 表示，当前有 k 个鸡蛋，可以尝试扔 m 次鸡蛋，
     * 这个条件下最坏情况下最多能确切测试一栋 n 层的楼
     * 首先确定状态，当前拥有的鸡蛋数k和需要测试的楼层数n；随着测试的进行，鸡蛋数可能减少，楼层的扫描数会减少，这是状态的变化
     * 然后确定选择：选择在哪层扔鸡蛋
     * base case：n==0，不要扔鸡蛋，返回0；k==1，只剩一个鸡蛋需要扫描全楼层，返回n
     *
     * @param k
     * @param n
     * @return
     */
    // O(K*N^2)/O(KN)
    public int superEggDrop(int k, int n) {
        // 当前有k个鸡蛋，最多扔n个鸡蛋，dp值需要搜索的楼层数
        int[][] dp = new int[k + 1][n + 1];
        // 最少扔鸡蛋数
        int m = 0;
        // 扫描n层楼
        while (dp[k][m] < n) {
            // 扔鸡蛋测试
            m++;
            for (int i = 1; i <= k; i++) {
                // 一共有i个鸡蛋，至少需要扔m个测试。上一个状态：扔的鸡蛋数-1，鸡蛋没碎需要扫描楼层数+鸡蛋碎了扫描的楼层数+扫描当前楼
                dp[i][m] = dp[i][m - 1] + dp[i - 1][m - 1] + 1;
            }
        }
        return m;
    }

    /**
     * 10. 正则表达式匹配
     * https://leetcode.cn/problems/regular-expression-matching/
     * 方法：动态规划
     * 思路：首先定义的指针i和j分别指向字符串s和p移动，状态转移方程dp(s,i,p,j)：表示s[i...]是否可以匹配p[j...]。
     * 首先显示判断两个字符是否匹配包括.进行比较，在匹配和不匹配的两个判断的分支中进行判断j的下一个索引位置的值是否是*。
     * 所以总的的判断分支就会是4个。
     * base case这里的定义不是很好理解，j走到头，批判i是不是也走到头;不是说i==s.length然后接着判断j==p.length就可以了。
     * 即就算把s匹配完了，但是p还是会继续向后匹配。只要p[j..]能够匹配空串，就可以算完成匹配。比如说s = "a", p = "ab*c*"，
     * 当i走到s末尾的时候，j并没有走到p的末尾，但是p依然可以匹配s。
     *
     * @param s
     * @param p
     * @return
     */
    // O(m*n)/O(m*n)
    int[][] memo5;

    public boolean isMatch(String s, String p) {
        int m = s.length(), n = p.length();
        memo5 = new int[m][n];
        for (int[] row : memo5) {
            Arrays.fill(row, -1);
        }
        return dp6(s, 0, p, 0);
    }

    private boolean dp6(String s, int i, String p, int j) {
        // base case
        if (j == p.length()) {
            return i == s.length();
        }
        // 如果能匹配空串，一定是字符和 * 成对儿出现
        if (i == s.length()) {
            if (j % 2 == 1) {
                return false;
            }
            // 检查是否为 x*y*z* 这种形式
            for (; j < p.length(); j += 2) {
                if (p.charAt(j + 1) != '*') {
                    return false;
                }
            }
            return true;
        }

        // 备忘录，防止重复计算
        if (memo5[i][j] != -1) {
            return memo5[i][j] == 1;
        }

        // 状态转移方程
        boolean res = false;
        if (s.charAt(i) == p.charAt(j) || '.' == p.charAt(j)) {
            if (j < p.length() - 1 && p.charAt(j + 1) == '*') {
                res = dp6(s, i, p, j + 2) || dp6(s, i + 1, p, j);
            } else {
                res = dp6(s, i + 1, p, j + 1);
            }
        } else {
            if (j < p.length() - 1 && p.charAt(j + 1) == '*') {
                res = dp6(s, i, p, j + 2);
            } else {
                res = false;
            }
        }
        memo5[i][j] = res ? 1 : 0;
        return res;
    }

    /**
     * 514. 自由之路
     * https://leetcode.cn/problems/freedom-trail/
     * 方法：动态规划
     * 思路：确定状态：状态是当前输入的字符以及当前圆盘指针指向的位置。
     * 定义dp函数：表示至少需要的操作次数，dp(rang,i,key,j)，i 表示当前圆盘上指针指向的字符（也就是 ring[i]）；j 表示需要输入的字符（也就是 key[j]）
     * 当圆盘指针指向rang[i]时，输入字符串key[j...]至少需要dp(rang,i,key,j)次操作。
     * 注意：拨动指针分成正向和逆向，所以按照逆向波动指针的步数=ring.length-正向波动指针的步数
     * base case：j==key.length
     * 确保每次步骤都是最佳的，最后算出的结果就是最佳的值。
     * 备忘录：key中的字母有重复的情况，所以会出现重复计算的情况，此时加入备忘录避免重复的计算
     *
     * @param ring
     * @param key
     * @return
     */
    // O(m*n)/(m*n)
    // 备忘录
    int[][] memo4;
    // 字符 -> 索引列表
    Map<Character, List<Integer>> charToIndex = new HashMap<>();

    public int findRotateSteps(String ring, String key) {
        // 备忘录全部初始化为 0
        memo4 = new int[ring.length()][key.length()];
        // 记录圆环上字符到索引的映射
        for (int i = 0; i < ring.length(); i++) {
            char c = ring.charAt(i);
            if (!charToIndex.containsKey(c)) {
                charToIndex.put(c, new ArrayList<>());
                charToIndex.get(c).add(i);
            }
            charToIndex.get(c).add(i);
        }
        // 圆盘指针最初指向 12 点钟方向，从第一个字符开始输入 key
        return dp5(ring, 0, key, 0);
    }

    // 计算圆盘指针在 ring[i]，输入 key[j..] 的最少操作数
    private int dp5(String ring, int i, String key, int j) {
        // base case 输入的字符串已将遍历完毕
        if (key.length() == j) {
            return 0;
        }

        // 查找备忘录，避免重叠子问题
        if (memo4[i][j] != 0) {
            return memo4[i][j];
        }

        // 做选择，状态转移
        int n = ring.length();
        int res = Integer.MAX_VALUE;
        // ring 上可能有多个字符 key[j]
        for (int k : charToIndex.get(key.charAt(j))) {
            // k为选择字符所在ring的位置，计算正向需要拨动指针次数，注意取绝对值
            int step = Math.abs(i - k);
            // 选择顺时针还是逆时针
            step = Math.min(step, n - step);

            // 选择「整体」操作次数最少的，加一是因为按动按钮也是一次操作
            // 避免计算的步骤超限  主要这里传递不是i是k，因为要计算重复目标字符的最终操作数
            res = Math.min(dp5(ring, k, key, j + 1) + step + 1, res);
        }
        // 将当前选择的最终结果放入备忘录中
        memo4[i][j] = res;
        return memo4[i][j];
    }

    /**
     * 174. 地下城游戏
     * https://leetcode.cn/problems/dungeon-game/description/
     * 方法：动态规划（自上而下递归）
     * 思路：定义dp函数：走到当前位置的需要的最小生命值，动态转移方程需要考虑的是下一步应该往哪里走，也就是通过计算下一步的
     * 的最小生命值来决定当前的最小生命值。这个和之前的最小路径和是很不一样的点，因为最小路径和需要保证每一步算的值最小，走到最后
     * 的结果值就是最小的。所以这里的状态转移方程：
     * int res = Math.min(dp(dungeon,i+1,j),dp(dungeon,i,j+1))-dungeon[i][j]
     * dp(i,j) = res <= 0?1:res;
     * base case：i==m-1 && j==n-1 保证生命值不会小于等于0; i==m || j==n 处理走到边界的情况，返回Integer.VALUE_MAX
     * 备忘录：状态转移过程中会出现计算相同状态的情况，所以此处需要使用备忘录去重计算
     *
     * @param dungeon
     * @return
     */
    // O(m*n)/O(m*n)
    int[][] memo1;

    public int calculateMinimumHP(int[][] dungeon) {
        memo1 = new int[dungeon.length][dungeon[0].length];
        for (int[] row : memo1) {
            Arrays.fill(row, -1);
        }
        return dp4(dungeon, 0, 0);
    }

    private int dp4(int[][] dungeon, int i, int j) {
        int m = dungeon.length, n = dungeon[0].length;
        // base case
        // 处理走到边界的情况
        if (i == m - 1 && j == n - 1) {
            // 处理走到最后一个节点的前一步的最小生命值1
            return dungeon[i][j] >= 0 ? 1 : -dungeon[i][j] + 1;
        }
        // 处理走到最后一个节点的情况
        if (i == m || j == n) {
            // 保证走出边界的时候，返回一个最大的数，保证上一步的最小生命值不变
            return Integer.MAX_VALUE;
        }
        // 备忘录 处理状态的重复计算
        if (memo1[i][j] != -1) {
            return memo1[i][j];
        }
        // 状态转移方程：下一步的最小生命值计算当前的最小生命值
        int res = Math.min(dp4(dungeon, i + 1, j), dp4(dungeon, i, j + 1)) - dungeon[i][j];
        // 保证生命值至少为1
        memo1[i][j] = res <= 0 ? 1 : res;
        return memo1[i][j];
    }

    /**
     * 188. 买卖股票的最佳时机 IV
     * https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iv/
     * 方法：动态规划+状态机
     * 思路：定义一个三维数组dp[n][k][m]，dp：最大的利润，其中n：天数；k：允许交易的最大次数；m：当前持有的状态，分为两种
     * 1表示持有，0表示没有持有。状态转移0->1：买入-prices[i] 1->0：卖出+prices[i]
     * k是个未知数，需要判断他的请款，如果比n天内最大的交易次数多（k>n/2），需要按照k为无限次进行处理；如果小于这个范围直接将k次交易状态值计算出来
     * 状态转移方程：
     * dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
     * dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i]))
     *
     * @param k
     * @param prices
     * @return
     */
    // O(n*k)/O(n*k)
    public int maxProfit3(int k, int[] prices) {
        int n = prices.length;
        if (k > n / 2) {
            // 复用之前交易次数 k 没有限制的情况
            return maxProfitKInf(prices);
        }
        int[][][] dp = new int[n][k + 1][2];
        // 下面的处理情况没有交易次数==0的情况，在上面的base case中处理
        for (int i = 0; i < n; i++) {
            for (int j = k; j > 0; j--) {
                // base case
                if (i == 0) {
                    dp[i][j][0] = 0;
                    dp[i][j][1] = -prices[i];
                    continue;
                }
                dp[i][j][0] = Math.max(dp[i - 1][j][0], dp[i - 1][j][1] + prices[i]);
                // 买入k-1
                dp[i][j][1] = Math.max(dp[i - 1][j - 1][0] - prices[i], dp[i - 1][j][1]);
            }
        }
        return dp[n - 1][k][0];
    }

    private int maxProfitKInf(int[] prices) {
        int n = prices.length;
        int dp_0 = 0, dp_1 = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            int temp = dp_0;
            dp_0 = Math.max(dp_0, dp_1 + prices[i]);
            dp_1 = Math.max(temp - prices[i], dp_1);
        }
        return dp_0;
    }


    /**
     * 123. 买卖股票的最佳时机 III
     * https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iii/
     * 方法2：动态规划+临时变量存储相邻状态
     * 思路：定义一个三维数组dp[n][k][m]，dp：最大的利润，其中n：天数；k：允许交易的最大次数；m：当前持有的状态，分为两种
     * 1表示持有，0表示没有持有。状态转移0->1：买入-prices[i] 1->0：卖出+prices[i]
     * k=2，限定的交易次数是2次，直接把 k = 1 和 2 的情况全部列举
     * 状态转移方程：
     * dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
     * dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])
     * 因为当前结果值之和前一个状态的值有关系，不需要整个dp数组，只需要一个变量存储相邻的那个状态就可以了，这样可以把空间复杂度降低到O(1)
     *
     * @param prices
     * @return
     */
    // O(n)/O(1)
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int dp_10 = 0, dp_11 = Integer.MIN_VALUE;
        int dp_20 = 0, dp_21 = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            // 第二次交易
            dp_20 = Math.max(dp_20, dp_21 + prices[i]);
            dp_21 = Math.max(dp_10 - prices[i], dp_21);
            // 第一次交易
            dp_10 = Math.max(dp_10, dp_11 + prices[i]);
            dp_11 = Math.max(-prices[i], dp_11);
        }
        return dp_20;
    }

    /**
     * 123. 买卖股票的最佳时机 III
     * https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iii/
     * 方法1：动态规划+状态机
     * 思路：定义一个三维数组dp[n][k][m]，dp：最大的利润，其中n：天数；k：允许交易的最大次数；m：当前持有的状态，分为两种
     * 1表示持有，0表示没有持有。状态转移0->1：买入-prices[i] 1->0：卖出+prices[i]
     * k=2，限定的交易次数是2次 base case：i==0的，两个状态的初始值
     * 状态转移方程：
     * dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
     * dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i]))
     *
     * @param prices
     * @return
     */
    // O(n)/O(n)
    public int maxProfit2(int[] prices) {
        int n = prices.length;
        int max_k = 2;
        int[][][] dp = new int[n][max_k + 1][2];
        for (int i = 0; i < n; i++) {
            for (int k = max_k; k > 0; k--) {
                if (i == 0) {
                    // base case：
                    dp[i][k][0] = 0;
                    dp[i][k][1] = -prices[i];
                    continue;
                }
                dp[i][k][0] = Math.max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i]);
                dp[i][k][1] = Math.max(dp[i - 1][k - 1][0] - prices[i], dp[i - 1][k][1]);
            }
        }
        // 取最后一次，交易第2次后，卖出股票的利润值
        return dp[n - 1][max_k][0];
    }

    /**
     * 140. 单词拆分 II
     * 思路：定义dp(s,i)为是s匹配上word单词构成的句子，i是匹配s前缀的一个单词在s中的索引。状态转移方程：在给定的单词集合
     * 中有单词可以是s的前缀部分，此时下一个状态是从匹配了单词的下一个位置去继续寻找，直到i==s.length()。个人理解就是截取s中的单词去匹配
     * word集合中的单词，一直遍历到s的完毕还能匹配上就是找到了，因为只有保证上一个部分片段匹配上才能进行下一次的匹配。
     * base case：i==s.length()
     * 使用备忘录消除重叠子问题
     *
     * @param s
     * @param wordDict
     * @return
     */
    // O(m^3)/O(n)  m:s的长度  n:wordDict个数
    // 备忘录
    List<String>[] memo3;
    Set<String> wordSet = null;

    public List<String> wordBreak(String s, List<String> wordDict) {
        memo3 = new ArrayList[s.length()];
        wordSet = new HashSet<>(wordDict);
        return dp3(s, 0);
    }

    // 定义：返回用 wordDict 构成 s[i..] 的所有可能
    private List<String> dp3(String s, int i) {
        List<String> res = new ArrayList<>();
        // base case
        if (i == s.length()) {
            res.add("");
            return res;
        }
        // 防止冗余计算
        if (memo3[i] != null) {
            return memo3[i];
        }
        // 遍历 s[i..] 的所有前缀
        for (int len = 1; i + len <= s.length(); len++) {
            // 看看哪些前缀存在 wordDict 中
            String prefix = s.substring(i, i + len);
            if (wordSet.contains(prefix)) {
                // 找到一个单词匹配 s[i..i+len)
                List<String> subProblem = dp3(s, i + len);
                // 构成 s[i+len..] 的所有组合加上 prefix
                // 就是构成构成 s[i] 的所有组合
                for (String sub : subProblem) {
                    if (sub.isEmpty()) {
                        // 防止多余的空格
                        res.add(prefix);
                    } else {
                        // 后序位置，当前的prefix去拼接子结果
                        res.add(prefix + " " + sub);
                    }
                }
            }
        }
        // 存入备忘录
        memo3[i] = res;
        return res;
    }

    /**
     * 剑指 Offer II 097. 子序列的数目
     * 方法：动态规划
     * 思路：定义dp(s,i,t,j)为子序列的数目，状态转移方程：s[i]==s[j]匹配上目标子序列的字符时需要考虑s字符串中相邻字符相等的情况，
     * 若相等，下一个状态中计算s下一个字符和t的当前字符结果值+s下一个字符和t的下一个字符结果值
     * 若不相等，计算s的下一个字符与t的当前字符结果值
     * base case1: t.length()==j
     * base case2: s.length()-i<t.length()-j
     * 备忘录消息重叠子问题
     *
     * @param s
     * @param t
     * @return
     */
    int[][] memo2;

    // O(m*n)/O(m*n)
    public int numDistinct2(String s, String t) {
        memo2 = new int[s.length()][t.length()];
        for (int[] row : memo2) {
            Arrays.fill(row, -1);
        }
        return dp2(s, 0, t, 0);
    }

    private int dp2(String s, int i, String t, int j) {
        // base case1
        if (t.length() == j) {
            return 1;
        }
        // base case2
        if (s.length() - i < t.length() - j) {
            return 0;
        }
        // 备忘录消除重叠子问题
        if (memo2[i][j] != -1) {
            return memo2[i][j];
        }
        int res = 0;
        // 状态转移方程
        if (s.charAt(i) == t.charAt(j)) {
            res += dp2(s, i + 1, t, j + 1) + dp2(s, i + 1, t, j);
        } else {
            res += dp2(s, i + 1, t, j);
        }
        memo2[i][j] = res;
        return res;
    }

    /**
     * 115. 不同的子序列
     * https://leetcode.cn/problems/distinct-subsequences/
     * 方法：动态规划
     * 思路：利用球盒模型中以球为视角解题，以盒子为视角解题时间复杂度会很高。这里s是若干小球，t是若干盒子，球的数量>=盒子的数量
     * 定义s[i...]的子序列中t[j...]出现的次数为dp[s,i,t,j]，状态转移方程s[i]==s[j]，若匹配到的目标子序列中的字符，然后计算下一个状态，让s的下一个
     * 字符匹配t的当前字符结果+s的下一个字符匹配t的下一个字符结果。【因为s的相邻字符会出现相同的情况】
     * 若不匹配，继续计算s的下一个字符，t的字符索引不动。
     * base case1：j==t.length()
     * base case2：s.length()-i<t.length()-j
     * 加入备忘录排除状态出现重复的情况
     *
     * @param s
     * @param t
     * @return
     */
    // O(m*n)/O(m*n)
    int memo[][];

    public int numDistinct(String s, String t) {
        memo = new int[s.length()][t.length()];
        // 初始化备忘录为特殊值 -1
        for (int[] row : memo) {
            Arrays.fill(row, -1);
        }
        return dp(s, 0, t, 0);
    }

    private int dp(String s, int i, String t, int j) {
        // base case1
        if (j == t.length()) {
            // t 已经全部匹配完成
            return 1;
        }
        // base case2
        if (s.length() - i < t.length() - j) {
            // s[i..] 比 t[j..] 还短，必然没有匹配的子序列
            return 0;
        }
        // 查备忘录防止冗余计算
        if (memo[i][j] != -1) {
            return memo[i][j];
        }
        int res = 0;
        if (s.charAt(i) == t.charAt(j)) {
            // 匹配，两种情况，累加关系
            res += dp(s, i + 1, t, j + 1) + dp(s, i + 1, t, j);
        } else {
            // 不匹配，在 s[i+1..] 的子序列中计算 t[j..] 的出现次数
            res += dp(s, i + 1, t, j);
        }
        memo[i][j] = res;
        return res;
    }

    /**
     * 1312. 让字符串成为回文串的最少插入次数
     * 方法：动态规划
     * 思路：这道题实际上可以联系到求最长回文子序列这道题上，n-最长回文子序列数量即为最长回文串的最少插入次数。
     * 最长回文子序列长度：利用二维数组解题，在子序列中s[i][j]，最长回文子串的长度dp[i][j]，个人理解为是两个指针的移动，两个指针之间的序列是
     * 回文串，从尾端左指针向前移动，每次固定左指针，然后右指针在当前位置向后移动，dp数组记录的就是指针当前状态的结果。判断两个位置的元素
     * 是不是相等的，如果相等两个指针前后分别移动，如果不相等移动二者指针其一取最大状态的结果。
     * 动态转移就是去更新这个回文串的长度。base case：1，同时。从末端往前移动的原因是动态转移的过程中涉及到
     * dp[i + 1][j - 1]、dp[i+1][j]、dp[i][j-1]三个状态
     *
     * @param s
     * @return
     */
    // O(n^2)/O(n^2)
    public int minInsertions(String s) {
        int n = s.length();
        // base case：dp数组对角线初始化为1
        int[][] dp = new int[n][n];
        for (int i = 0; i < n; i++) {
            // 初始化两个指针同时指向一个位置的值
            dp[i][i] = 1;
        }
        // 反着遍历保证正确的转移状态
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i + 1; j < n; j++) {
                // 状态转移方程
                if (s.charAt(j) == s.charAt(i)) {
                    dp[i][j] = dp[i + 1][j - 1] + 2;
                } else {
                    dp[i][j] = Math.max(dp[i][j - 1], dp[i + 1][j]);
                }
            }
        }
        // 整个s的最长回文子串的长度
        return n - dp[0][n - 1];
    }


    /**
     * 动态规划之KMP算法
     * 思路：后者是在txt中匹配pat，前者是在pat中匹配pat[1:]，状态X总是落后状态j一个状态，与j具有最长的相同前缀。所以我把X比喻为影子状态，
     * 所谓影子状态，就是和当前状态具有相同的前缀。
     * 如果遇到的字符c和pat[j]匹配的话，状态就应该向前推进一个，也就是说next = j + 1；如果遇到的字符c和pat[j]不匹配的话，状态就要回退。
     * 因为状态X和状态j存在相同的前缀，所以当状态j准备进行状态重启的时候（遇到的字符c和pat[j]不匹配），可以通过X的状态转移图来获得最近的重启位置。
     * 状态转移：状态j会把这个字符委托给状态X处理，也就是dp[j]['A'] = dp[X]['A']
     *
     * @param txt
     * @param pat
     * @return
     */

    // O(256*m)/O(256*n)
    public int KMP(String txt, String pat) {
        int m = pat.length();
        // dp[状态][字符] = 下个状态
        int[][] dp = new int[m][256];
        // 预置dp数组的值
        // base case
        dp[0][pat.charAt(0)] = 1;
        // 影子状态 X 初始为 0
        int x = 0;
        // 构建状态转移图（稍改的更紧凑了）
        for (int j = 1; j < m; j++) {
            for (char c = 0; c < 256; c++) {
                if (pat.charAt(j) == c) {
                    dp[j][c] = j + 1;
                } else {
                    dp[j][c] = dp[x][c];
                }
            }
            x = dp[x][pat.charAt(j)];
        }

        int n = txt.length();
        // pat 的初始态为 0
        int j = 0;
        for (int i = 0; i < n; i++) {
            // 计算 pat 的下一个状态
            j = dp[i][txt.charAt(i)];
            if (j == m) {
                // 到达终止态，返回结果 注意这里j是从0取值的，所以这里要+1
                return n - m + 1;
            }
        }
        // 没到达终止态，匹配失败
        return -1;
    }

    /**
     * 354. 俄罗斯套娃信封问题
     * https://leetcode.cn/problems/russian-doll-envelopes/
     * 方法：最长递增子序列（耐心排序+二分查找法）
     * 思路：假设信封的宽度和高度组成由二维数(w,h)对来表示，先对宽度w进行升序排列，遇到相同的w再按照h进行降序排列，之后按照h最为一个数组，
     * 在该数组上计算LIS的长度就是答案。
     * 【首先，对宽度 w 从小到大排序，确保了 w 这个维度可以互相嵌套，所以我们只需要专注高度 h 这个维度能够互相嵌套即可。
     * 其次，两个 w 相同的信封不能相互包含，所以对于宽度 w 相同的信封，对高度 h 进行降序排序，保证二维 LIS 中不存在多个 w 相同的信封（因为题目说了长宽相同也无法嵌套）。】
     *
     * @param envelopes
     * @return
     */

    // O(NlogN)/O(N)
    // O(NlogN)：lengthOfLIS的时间复杂度是O(NlogN)，因为排序和计算 LIS 各需要 O(NlogN) 的时间，加到一起还是 O(NlogN)
    // O(N)：计算 LIS 的函数中需要一个 top 数组。
    public int maxEnvelopes(int[][] envelopes) {
        // 按宽度升序排列，如果宽度一样，则按高度降序排列
        Arrays.sort(envelopes, (arr1, arr2) -> {
            // 二维数组比较大小，当第一维相等时比较第二维。谁大谁在前（arr2[1] - arr1[1]）
            return arr1[0] == arr2[0] ? arr2[1] - arr1[1] : arr1[0] - arr2[0];
        });
        int[] height = new int[envelopes.length];
        for (int i = 0; i < envelopes.length; i++) {
            height[i] = envelopes[i][1];
        }
        // 寻找列数据的最长递增子序列的长度，利用二分查找找出升序的堆顶元素集合中最左侧的扑克放置位置
        int piles = 0;
        int[] top = new int[height.length];
        for (int i = 0; i < top.length; i++) {
            int poker = height[i];
            // 二分查找
            int left = 0, right = piles;
            while (left < right) {
                // 防止了left和right太大直接相加导致溢出
                int mid = left + (right - left) / 2;
                if (top[mid] > poker) {
                    right = mid;
                } else if (top[mid] < poker) {
                    left = mid + 1;
                } else {
                    right = mid;
                }
            }
            // 左指针一直往右走，达到堆数，表示没找到
            if (left == piles) {
                piles++;
            }
            // 把牌放到堆上
            top[left] = poker;
        }
        return piles;
    }

    /**
     * 剑指 Offer II 017. 含有所有字符的最短字符串
     * https://leetcode.cn/problems/M1oyTv/
     * 方法：滑动窗口
     * 思路：定义两个Map，其中一个存储t的所有字符，以及对应的个数，目的是在窗口滑动的窗口中寻找到对应的子串；另一个是存储窗口中符合条件的字符
     * 窗口缩小的条件是窗口中的不重复字符的个数>need的长度
     * z注意：len取Integer的最大值
     *
     * @param s
     * @param t
     * @return
     */
    public String minWindow2(String s, String t) {
        Map<Character, Integer> need = new HashMap<>();
        Map<Character, Integer> window = new HashMap<>();
        for (char c : t.toCharArray()) {
            need.put(c, need.getOrDefault(c, 0) + 1);
        }
        int left = 0, right = 0;
        int valid = 0;
        int len = Integer.MAX_VALUE, start = 0;
        while (right < s.length()) {
            char c = s.charAt(right);
            right++;
            if (need.containsKey(c)) {
                window.put(c, window.getOrDefault(c, 0) + 1);
                if (window.get(c).equals(need.get(c))) {
                    valid++;
                }
            }
            while (valid == need.size()) {
                if (right - left < len) {
                    start = left;
                    len = right - left;
                }
                char d = s.charAt(left);
                left++;
                if (need.containsKey(d)) {
                    if ((window.get(d).equals(need.get(d)))) {
                        // 窗口中的d字符移出之后，就不符合need中存在符合条件的d字符了
                        valid--;
                    }
                    window.put(d, window.get(d).intValue() - 1);
                }
            }
        }
        return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);
    }

    /**
     * 370. 区间加法
     * https://leetcode.cn/problems/range-addition/
     * 方法：差分数组
     * 思路：每一次的操作都是针对给定区间范围nums[i,j]的数值进行+/-val。
     * 1.先求出差分数组，即相邻元素之差（后-前）
     * 2.操作差分数组，diff[i]+val，diff[j+1]-val。这里可理解成nums[i]-nums[i-1]，减数不变，被减数+val，为保持相邻元素之差不变，i位置以后的值
     * 全部被+val，此时我们需要的只是[i,j]这个区间的数值+val，所以需要diff[j+1]-val。
     * 3.求出结果数组，将差分数组还原，即求被减数的过程。res[i]+nums[i]
     *
     * @param length
     * @param updates
     * @return
     */
    // O(n+m)，其中 n 为要求的数组长度，m 更改次数。
    // O(1)
    public int[] getModifiedArray(int length, int[][] updates) {
        // nums 初始化为全 0
        int[] nums = new int[length];
        // 构造差分解法
        Difference difference = new Difference(nums);
        for (int[] update : updates) {
            int i = update[0];
            int j = update[1];
            int val = update[2];
            difference.increment(i, j, val);
        }
        return difference.result();
    }


    // 差分数组工具类
    private class Difference {

        // 差分数组
        private int[] diff;

        /**
         * 初始化查分数组
         * 输入一个初始数组，区间操作将在这个数组上进行
         *
         * @param nums
         */
        public Difference(int[] nums) {
            if (nums.length == 0) {
                return;
            }
            diff = new int[nums.length];
            // 根据初始数组构造差分数组
            diff[0] = nums[0];
            for (int i = 1; i < nums.length; i++) {
                diff[i] = nums[i] - nums[i - 1];
            }
        }

        /**
         * 给闭区间 [i, j] 增加 val（可以是负数）
         *
         * @param i
         * @param j
         * @param val
         */
        public void increment(int i, int j, int val) {
            diff[i] += val;
            int next = j + 1;
            if (next < diff.length) {
                diff[next] -= val;
            }
        }

        /**
         * 返回结果数组
         *
         * @return
         */
        public int[] result() {
            int[] res = new int[diff.length];
            // 根据差分数组构造结果数组
            res[0] = diff[0];
            for (int i = 1; i < res.length; i++) {
                res[i] = res[i - 1] + diff[i];
            }
            return res;
        }
    }

    /**
     * 51. N 皇后
     * https://leetcode.cn/problems/n-queens/
     * 方法：回溯+决策树
     * 思路：首先初始化棋盘，也就是给每个位置都放置为.。调用回溯方法，触发的结束条件是，当row等于棋盘的宽度时，
     * 遍历整个棋盘，将本次一个树枝上的结果保存到结果集合中去。遍历所有列，排除掉不能放皇后的列【只用检查上面，左上，右上三个方向】，
     * 剩下当前行可能选择的列，放置Q，继续进行下一行的决策。决策完之后，需要撤销选择【若不理解，可以看全排列讲解的图】
     */

    //O(n×n!)/O(n)  n是皇后数量
    List<List<String>> res = new ArrayList<>();
    char[][] board;
    int len;

    public List<List<String>> solveNQueens(int n) {
        // 创建棋盘，每个位置置为.
        board = new char[n][n];
        len = n;
        for (char[] cArray : board) {
            Arrays.fill(cArray, '.');
        }
        // 调用回溯方法
        backTrack(0);
        return res;
    }

    // 路径：board 中小于 row 的那些行都已经成功放置了皇后
    // 选择列表：第 row 行的所有列都是放置皇后的选择
    // 结束条件：row 超过 board 的最后一行
    private void backTrack(int row) {
        // 触发结束条件
        if (row == len) {
            // 将棋盘各个位置上的值全部存入一个集合，表示一种可能放置的结果
            List<String> oneRes = new ArrayList<>();
            for (char[] cArray : board) {
                oneRes.add(new String(cArray));
            }
            res.add(oneRes);
            return;
        }

        // 遍历当前行的所有列，即选择列表
        for (int col = 0; col < len; col++) {
            // 排除不合法的选择
            if (!isValid(row, col)) {
                continue;
            }
            // 做选择
            board[row][col] = 'Q';
            // 进入下一行决策
            backTrack(row + 1);
            // 撤销选择
            board[row][col] = '.';
        }
    }

    // 是否可以在 board[row][col] 放置皇后？
    // 只检查了左上角，右上角和上方的格子原因：因为皇后是一行一行从上往下放的，所以左下方，
    // 右下方和正下方不用检查（还没放皇后）；因为一行只会放一个皇后，所以每行不用检查。也就
    // 是最后只用检查上面，左上，右上三个方向。
    private boolean isValid(int row, int col) {
        // 检查列上方是否有皇后互相冲突
        for (int i = 0; i <= row; i++) {
            if (board[i][col] == 'Q') {
                return false;
            }
        }
        // 检查右上方是否有皇后互相冲突
        for (int i = row - 1, j = col + 1; i >= 0 && j < len; i--, j++) {
            if (board[i][j] == 'Q') {
                return false;
            }
        }
        // 检查左上方是否有皇后互相冲突
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            if (board[i][j] == 'Q') {
                return false;
            }
        }
        return true;
    }

    /**
     * 剑指 Offer 51. 数组中的逆序对
     * 方法：归并排序
     * 思路：与（315. 计算右侧小于当前元素的个数）同，区别在于这个题求得不是各个元素比其小的元素个数，而是求得所有情况的总数。既然这道题比315题
     * 简单一些，所以不需要创建Pair对象了，直接求出所有元素比其小的元素的情况总数即可。
     *
     * @param nums
     * @return
     */
    // O(Nlog(N))/O(N)
    int[] temp4;

    public int reversePairs2(int[] nums) {
        // 注意防控判断
        if (nums == null || nums.length == 0) {
            return 0;
        }
        temp4 = new int[nums.length];
        return sort2(nums, 0, nums.length - 1);
    }

    // 归并排序
    private int sort2(int[] arr, int low, int high) {
        if (low == high) {
            return 0;
        }
        int mid = low + (high - low) / 2;
        int left = sort2(arr, low, mid);
        int right = sort2(arr, mid + 1, high);
        // B数组比A数组的值都大，那么后面的cur=0，也就不用调用merge方法了
        if (arr[mid] <= arr[mid + 1]) {
            return left + right;
        }
        int cur = merge2(arr, low, mid, high);
        return left + cur + right;
    }

    private int merge2(int[] arr, int low, int mid, int high) {
        for (int i = low; i <= high; i++) {
            temp4[i] = arr[i];
        }
        int i = low, j = mid + 1;
        int count = 0;
        for (int p = low; p <= high; p++) {
            if (i == mid + 1) {
                arr[p] = temp4[j++];
            } else if (j == high + 1) {
                arr[p] = temp4[i++];
                count += j - mid - 1;
            } else if (temp4[i] > temp4[j]) {
                arr[p] = temp4[j++];
            } else {
                arr[p] = temp4[i++];
                count += j - mid - 1;
            }
        }
        return count;
    }

    /**
     * 42. 接雨水
     * https://leetcode.cn/problems/trapping-rain-water/
     * 方法：双指针
     * 思路：左右两个指针相向而行，每次计算[0,left]，[0,right]两个区间的最高柱子的高度，分别是lMax，rMax，
     * 然后计算出二者的最小值，使用这个最小的柱子高度-最小柱子高度区间的指针所指向的柱子的高度，就是当前指针指向位置可以
     * 接的雨水量
     *
     * @param height
     * @return
     */
    // O(n)/(1)
    public int trap(int[] height) {
        // 因为是两个柱子之间才能接水
        int left = 0, right = height.length - 1;
        int lMax = 0, rMax = 0;
        int res = 0;
        while (left < right) {
            lMax = Math.max(height[left], lMax);
            rMax = Math.max(height[right], rMax);
            // res += min(l_max, r_max) - height[i]
            // 只有计算进结果的值指针才会移动
            if (lMax < rMax) {
                res += lMax - height[left];
                left++;
            } else {
                res += rMax - height[right];
                right--;
            }
        }
        return res;
    }

    /**
     * 327. 区间和的个数
     * https://leetcode.cn/problems/count-of-range-sum/
     * 方法：前缀和+归并排序
     * 思路：首先明白题意要求计算元素和落在 [lower, upper] 中的所有子数组的个数。首先计算出给定数组的前缀和数组，
     * preSum 中的两个元素之差其实就是区间和。在两个子数组排序后要进行合并的过程中，合并之前利用排好序的两个数组进行计算区间和的个数。
     * 利用滑动窗口，遍历子数组A，让数组B中的值减数组A中的值得到子区间和与给定的区间进行对比，直到窗口落到给定区间的范围内，求得区间和个数。
     *
     * @param nums
     * @param lower
     * @param upper
     * @return
     */
    //O(NlogN)/O(n)
    private int count3 = 0, lower, upper;

    // 构建前缀和数组，注意 int 可能溢出，用 long 存储
    public int countRangeSum(int[] nums, int lower, int upper) {
        this.lower = lower;
        this.upper = upper;
        long[] preSum = new long[nums.length + 1];
        for (int i = 0; i < nums.length; i++) {
            preSum[i + 1] = (long) nums[i] + preSum[i];
        }
        // 对前缀和数组进行归并排序
        sort(preSum);
        return count3;
    }

    // 归并排序
    private long[] temp3;

    private void sort(long[] nums) {
        temp3 = new long[nums.length];
        sort2(nums, 0, nums.length - 1);
    }

    private void sort2(long[] nums, int low, int high) {
        if (low == high) {
            return;
        }
        int mid = low + (high - low) / 2;
        sort2(nums, low, mid);
        sort2(nums, mid + 1, high);
        merge2(nums, low, mid, high);
    }

    private void merge2(long[] nums, int low, int mid, int high) {
        for (int i = low; i <= high; i++) {
            temp3[i] = nums[i];
        }
        // 维护左闭右开区间 [start, end) 中的元素和 nums[i] 的差在 [lower, upper] 中
        int start = mid + 1, end = mid + 1;
        for (int i = low; i <= mid; i++) {
            // 如果 nums[i] 对应的区间是 [start, end)，
            // 那么 nums[i+1] 对应的区间一定会整体右移，类似滑动窗口
            while (start <= high && nums[start] - nums[i] < lower) {
                start++;
            }
            while (end <= high && nums[end] - nums[i] <= upper) {
                end++;
            }
            count3 += end - start;
        }

        // 数组双指针技巧，合并两个有序数组
        int i = low, j = mid + 1;
        for (int p = low; p <= high; p++) {
            if (i == mid + 1) {
                nums[p] = temp3[j++];
            } else if (j == high + 1) {
                nums[p] = temp3[i++];
            } else if (temp3[i] > temp3[j]) {
                nums[p] = temp3[j++];
            } else {
                nums[p] = temp3[i++];
            }
        }
    }

    /**
     * 493. 翻转对
     * https://leetcode.cn/problems/reverse-pairs/
     * 方法：归并排序
     *
     * @param nums
     * @return
     */
    // 记录「翻转对」的个数
    private int count2 = 0;
    private int[] temp2;

    // O(NlogN)/O(N)
    public int reversePairs(int[] nums) {
        temp2 = new int[nums.length];
        sort(nums, 0, nums.length - 1);
        return count2;
    }

    // 归并排序
    private void sort(int[] nums, int low, int high) {
        if (low == high) {
            return;
        }
        int mid = low + (high - low) / 2;
        sort(nums, low, mid);
        sort(nums, mid + 1, high);
        merge(nums, low, mid, high);
    }

    private void merge(int[] nums, int low, int mid, int high) {
        for (int i = low; i <= high; i++) {
            temp2[i] = nums[i];
        }
        // 进行效率优化，维护左闭右开区间 [mid+1, end) 中的元素乘 2 小于 nums[i]
        // 为什么 end 是开区间？因为这样的话可以保证初始区间 [mid+1, mid+1) 是一个空区间
        int end = mid + 1;
        for (int i = low; i <= mid; i++) {
            // nums 中的元素可能较大，乘 2 可能溢出，所以转化成 long
            while (end <= high && (long) nums[i] > (long) nums[end] * 2) {
                end++;
            }
            count2 += end - mid - 1;
        }
        // 数组双指针技巧，合并两个有序数组
        int i = low, j = mid + 1;
        for (int p = low; p <= high; p++) {
            if (i == mid + 1) {
                nums[p] = temp2[j++];
            } else if (j == high + 1) {
                nums[p] = temp2[i++];
            } else if (temp2[i] > temp2[j]) {// 易错点
                nums[p] = temp2[j++];
            } else {
                nums[p] = temp2[i++];
            }
        }
    }

    /**
     * 315. 计算右侧小于当前元素的个数
     * https://leetcode.cn/problems/count-of-smaller-numbers-after-self/
     * 方法：归并排序
     * 思路：首先定义一个对象Pair去记录元素的值和元素在数组中所在的位置，遍历给定的数组nums，将其中的值赋值给Pair数组。
     * 通过归并排序，在这个合并有序子数组的过程中，temp[i++]赋值给arr[p]得地方(2处)都需要更新count数组
     */
//O(nlogn)/O(n)
    private class Pair {
        int val, id;

        Pair(int val, int id) {
            // 记录数组的元素值
            this.val = val;
            // 记录元素在数组中的原始索引
            this.id = id;
        }

    }

    // 归并排序所用的辅助数组
    private Pair[] temp;
    // 记录每个元素后面比自己小的元素个数
    private int[] count;

    // 主函数
    public List<Integer> countSmaller(int[] nums) {
        int n = nums.length;
        count = new int[n];
        temp = new Pair[n];
        Pair[] arr = new Pair[n];
        // 记录元素原始的索引位置，以便在 count 数组中更新结果
        for (int i = 0; i < n; i++) {
            arr[i] = new Pair(nums[i], i);
        }
        // 执行归并排序，本题结果被记录在 count 数组中
        sort(arr, 0, n - 1);
        List<Integer> result = new ArrayList<>();
        for (int c : count) {
            result.add(c);
        }
        return result;
    }

    // 归并排序
    private void sort(Pair[] arr, int low, int high) {
        if (low == high) {
            return;
        }
        int mid = low + (high - low) / 2;
        sort(arr, low, mid);
        sort(arr, mid + 1, high);
        merge(arr, low, mid, high);
    }

    // 合并两个有序数组
    private void merge(Pair[] arr, int low, int mid, int high) {
        for (int i = low; i <= high; i++) {
            temp[i] = arr[i];
        }
        int i = low, j = mid + 1;
        for (int p = low; p <= high; p++) {
            if (i == mid + 1) {
                arr[p] = temp[j++];
            } else if (j == high + 1) {
                arr[p] = temp[i++];
                //  更新 count 数组
                count[arr[p].id] += j - mid - 1;
            } else if (temp[i].val > temp[j].val) {
                arr[p] = temp[j++];
            } else {
                arr[p] = temp[i++];
                // 更新 count 数组
                count[arr[p].id] += j - mid - 1;
            }
        }
    }

    /**
     * 76. 最小覆盖子串
     * https://leetcode-cn.com/problems/minimum-window-substring/
     * 方法：双指针(快慢指针：滑动窗口)
     * 思路：1.将定义两个map集合，一个是目标字符串t中的字符存储到集合need中，key:value=字符:对应的个数。另一个
     * 是集合window存储窗口中满足目标字符串的字符和对应的数量。
     * 2.扩大窗口：滑动窗口是左右两个指针组合而成，右指针向前移动是扩大窗口，判断当前字符是否在need存在，如果存在，
     * 进行窗口内数量变更：window中对应的字符数量+1或存储该字符；该字符在window中存储的数量值和need存储数量值相同
     * valid++，表示找到了一个目标字符。
     * 3.收缩窗口：当valid达到need的key数量，即t中非重复字符数量，此时表示得到了一个解，需要收缩窗口，在收缩窗口的
     * 逻辑中判断是不是最优解，如果是就更新，不是不处理。然后收缩窗口就是将左指针前移，对应的字符在need中是否存在，如
     * 果存在，进行窗口内数量变更，需要更新valid（满足条件的字符不满足条件了，需要-1），然后将窗口中的目标字符集数量进
     * 行变更。
     *
     * @param s
     * @param t
     * @return
     */
    // O(C*|s|+|t|)/O(C)   C:表示map中字符集大小
    public static String minWindow(String s, String t) {
        // need:目标串字符集Map;window:窗口中目标串中字符集在窗口中的集合
        Map<Character, Integer> need = new HashMap<>();
        Map<Character, Integer> window = new HashMap<>();
        for (char c : t.toCharArray()) {
            need.put(c, need.getOrDefault(c, 0) + 1);
        }
        // 初始化各个变量 left:窗口左指针；right:窗口右指针；valid:记录t中不重复的字符个数临时变量。缩小窗口通过它判断
        int left = 0, right = 0, valid = 0;
        // 记录最小覆盖子串的起始索引和长度
        int start = 0, len = Integer.MAX_VALUE;
        while (right < s.length()) {
            // c是将移入窗口的字符
            char c = s.charAt(right);
            // 扩大窗口
            right++;
            // 进行窗口内数据的一系列更新
            if (need.containsKey(c)) {
                window.put(c, window.getOrDefault(c, 0) + 1);
                if (window.get(c).equals(need.get(c))) {
                    valid++;
                }
            }
            // 判断左侧窗口是否需要收缩
            while (valid == need.size()) {// 优化可行解
                // 更新覆盖子串
                if (right - left < len) {
                    start = left;
                    len = right - left;
                }
                // d是将移除窗口的字符
                char d = s.charAt(left);
                // 缩小窗口
                left++;
                // 进行窗口内数据的一系列更新
                if (need.containsKey(d)) {
                    if (window.get(d).equals(need.get(d))) {
                        valid--;
                    }
                    // 易错点 左移一位，只要need中包含此字符，window中的此字符数量就得-1
                    window.put(d, window.get(d).intValue() - 1);
                }
            }
        }
        return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);
    }

    /**
     * 4. 寻找两个正序数组的中位数
     * 方法一：归并排序
     * 思路：将两个有序数组合并，再根据合并数组后是奇数还是偶数返回中位数
     *
     * @param nums1
     * @param nums2
     * @return
     */
    // 时间复杂度：O(m+n) 空间复杂度：O(m+n)
    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        int nums[] = new int[m + n];
        // 处理边界问题
        // 1.其中一个数组是空的情况
        if (m == 0) {
            return n % 2 == 0 ? (nums2[n / 2 - 1] + nums2[n / 2]) / 2.0 : nums2[n / 2];
        }
        if (n == 0) {
            return m % 2 == 0 ? (nums1[m / 2 - 1] + nums1[m / 2]) / 2.0 : nums1[m / 2];
        }
        int count = 0, i = 0, j = 0;
        while (count != m + n) {
            // 2.m/n比n/m多出的元素
            if (i == m) {
                while (j != n) {
                    nums[count++] = nums2[j++];
                }
                break;
            }
            if (j == n) {
                while (i != m) {
                    nums[count++] = nums1[i++];
                }
                break;
            }
            if (nums1[i] < nums2[j]) {
                nums[count++] = nums1[i++];
            } else {
                nums[count++] = nums2[j++];
            }
        }
        return count % 2 == 0 ? (nums[count / 2 - 1] + nums[count / 2]) / 2.0 : nums[count / 2];
    }

}
